package cn.hesion.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

public class NextLargerNodes {

    public int[] nextLargerNodes(ListNode head) {
        ArrayList<Integer> list = new ArrayList<>();

        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        int[] res = new int[list.size()];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < list.size(); i++) {
            while (!stack.empty() && list.get(stack.peek()) < list.get(i)) {
               int index= stack.pop();
               res[index] = list.get(i);
            }
            stack.push(i);
        }
        return res;
    }

    public static void main(String[] args) {
        NextLargerNodes nextLargerNodes = new NextLargerNodes();
        int[] ints = nextLargerNodes.nextLargerNodes(
                new ListNode(2, new ListNode(7, new ListNode(4,new ListNode(3,new ListNode(5)))))
        );
        System.out.println(Arrays.toString(ints));
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
